home *** CD-ROM | disk | FTP | other *** search
/ Power Programmierung / Power-Programmierung (Tewi)(1994).iso / magazine / drdobbs / 1987 / 09 / stepplst.sep < prev   
Text File  |  1987-08-13  |  17KB  |  489 lines
  1. /*
  2. ** Copyright (c) 1987,  Tom Steppe.  All rights reserved.
  3. **
  4. ** This module compares two arrays of lines (representing
  5. ** files) and reports the sequences of consecutive matching
  6. ** lines between them using the "recursive longest matching
  7. ** sequence" algorithm.  This is useful for implementing a
  8. ** file comparison utility.
  9. **
  10. ** Compiler:  Microsoft (R) C Compiler  Version 4.00
  11. */
  12.  
  13. #include <stdio.h>
  14. #include <ctype.h>
  15. #include <string.h>
  16. #include <malloc.h>
  17.  
  18. /* Boolean type and values. */
  19. typedef int     BOOLEAN;
  20. #define TRUE    1
  21. #define FALSE   0
  22.  
  23. /* Minimum macro. */
  24. #define min(x, y)   (((x) <= (y)) ? (x) : (y))
  25.  
  26. /* Value to indicate identical strings with strcmp. */
  27. #define ALIKE   0
  28.  
  29. /* Result of hashing function for a line of text. */
  30. typedef unsigned int   HASH;
  31.  
  32. /* Mask for number of bits in hash code.  (12 bits). */
  33. #define MASK   (unsigned int) 0x0FFF
  34.  
  35. /* Number of possible hash codes. */
  36. #define HASHSIZ   (MASK + 1)
  37.  
  38. /* Information about an entry in a hash table. */
  39. typedef struct tblentry
  40. {
  41.     int   frst;   /* First line # with this hash code. */
  42.     int   last;   /* Last line # with this hash code. */
  43. } TBLENTRY;
  44.  
  45. /* Information about a line of text. */
  46. typedef struct lineinf
  47. {
  48.     HASH   hash;    /* Hash code value. */
  49.     int    nxtln;   /* Next line with same hash (or 0). */
  50. } LINEINF;
  51.  
  52. /* Information about a file. */
  53. typedef struct fileinf
  54. {
  55.     char       **txt;      /* Array of lines of text. */
  56.     LINEINF    *line;      /* Array of line info structs. */
  57.     TBLENTRY   *hashtbl;   /* Hash table. */
  58. } FILEINF;
  59.  
  60. /* Function declarations. */
  61. BOOLEAN filcmp      (char **, int, char **, int, int);
  62. BOOLEAN get_inf     (char **, int, FILEINF *);
  63. HASH    calc_hash   (char *);
  64. void    fnd_seq     (FILEINF *, int, int,
  65.                           FILEINF *, int, int, int);
  66. BOOLEAN chk_hashes  (LINEINF *, LINEINF *, int);
  67. int     cnt_matches (char **, char **, int);
  68. void    rpt_seq     (int, int, int);
  69.  
  70. /***********************************************************
  71. ** compare compares two arrays of lines and reports the
  72. ** sequences of consecutive matching lines.  The zeroth
  73. ** element of each array is unused so that the index into
  74. ** the array is identical to the associated line number.
  75. **
  76. ** RETURNS:  TRUE if comparison succeeded.
  77. **           FALSE if not enough memory.
  78. ***********************************************************/
  79.  
  80. BOOLEAN compare (a1, n1, a2, n2, lngval)
  81.  
  82. char   **a1;     /* (I) Array of lines of text in #1. */
  83. int    n1;       /* (I) Number of lines in a1.
  84.                         (Does not count 0th element.) */
  85. char   **a2;     /* (I) Array of lines of text in #2. */
  86. int    n2;       /* (I) Number of lines in a2.
  87.                         (Does not count 0th element.) */
  88. int    lngval;   /* (I) "Long enough" value. */
  89. {
  90.     FILEINF   f1;    /* File information for #1. */
  91.     FILEINF   f2;    /* File information for #2. */
  92.     BOOLEAN   rtn;   /* Return value. */
  93.  
  94.     /* Gather information for each file, then compare. */
  95.     if (rtn =
  96.         (get_inf (a1, n1, &f1) && get_inf (a2, n2, &f2)))
  97.     {
  98.         fnd_seq (&f1, 1, n1, &f2, 1, n2, lngval);
  99.     }
  100.  
  101.     return (rtn);
  102. }
  103.  
  104. /***********************************************************
  105. ** get_inf calculates hash codes and builds a hash table.
  106. **
  107. ** RETURNS:  TRUE if get_inf succeeded.
  108. **           FALSE if not enough memory.
  109. ***********************************************************/
  110.  
  111. static BOOLEAN get_inf (a, n, f)
  112.  
  113. char      **a;   /* (I) Array of lines of text. */
  114. int       n;     /* (I) Number of lines in a. */
  115. FILEINF   *f;    /* (O) File information. */
  116. {
  117.     unsigned int   size;     /* Size of hash table. */
  118.     register int   i;        /* Counter. */
  119.     TBLENTRY       *entry;   /* Entry in hash table. */
  120.  
  121.     /* Assign the array of text. */
  122.     f->txt = a;
  123.  
  124.     /* Allocate and initialize a hash table. */
  125.     size = HASHSIZ * sizeof (TBLENTRY);
  126.     if (f->hashtbl = (TBLENTRY *) malloc (size))
  127.     {
  128.         memset ((char *) f->hashtbl, '\0', size);
  129.     }
  130.     else
  131.     {
  132.         return (FALSE);
  133.     }
  134.  
  135.     /* If there are any lines: */
  136.     if (n > 0)
  137.     {
  138.         /* Allocate an array of line structures. */
  139.         if (f->line = (LINEINF *)
  140.                 malloc ((n + 1) * sizeof (LINEINF *)))
  141.         {
  142.             /* Loop through the lines. */
  143.             for (i = 1; i <= n; i++)
  144.             {
  145.                 /* Calculate the hash code value. */
  146.                 f->line[i].hash = calc_hash (f->txt[i]);
  147.  
  148.                 /* Locate the entry in the hash table. */
  149.                 entry = f->hashtbl + f->line[i].hash;
  150.  
  151.                 /* Update the linked list of lines with */
  152.                 /* the same hash code.                  */
  153.                 f->line[entry->last].nxtln = i;
  154.                 f->line[i].nxtln = 0;
  155.  
  156.                 /* Update the first and last line */
  157.                 /* information in the hash table. */
  158.                 if (entry->frst == 0)
  159.                 {
  160.                     entry->frst = i;
  161.                 }
  162.                 entry->last = i;
  163.             }
  164.         }
  165.         else
  166.         {
  167.             return (FALSE);
  168.         }
  169.     }
  170.     else
  171.     {
  172.        f->line = NULL;
  173.     }
  174.  
  175.     return (TRUE);
  176. }
  177.  
  178. /***********************************************************
  179. ** calc_hash calculates a hash code for a line of text.
  180. **
  181. ** RETURNS:  a hash code value.
  182. ***********************************************************/
  183.  
  184. static HASH calc_hash (buf)
  185.  
  186. char   *buf;   /* (I) Line of text. */
  187. {
  188.     register unsigned int   chksum;   /* Checksum. */
  189.     char                    *s;       /* Pointer. */
  190.     HASH                    hash;     /* Hash code value. */
  191.  
  192.     /* Build up a checksum of the characters in the text. */
  193.     for (chksum = 0, s = buf; *s; chksum ^= *s++)
  194.     {
  195.         ;
  196.     }
  197.  
  198.     /* Combine the 7-bit checksum and as much of the */
  199.     /* length as is possible.                        */
  200.     hash = ((chksum & 0x7F) | ((s - buf) << 7)) & MASK;
  201.  
  202.     return (hash);
  203. }
  204.  
  205. /***********************************************************
  206. ** Given starting and ending line numbers, fnd_seq finds a
  207. ** "good sequence" of lines within those ranges.  fnd_seq
  208. ** then recursively finds "good sequences" in the sections
  209. ** of lines above the "good sequence" and below it.
  210. ***********************************************************/
  211.  
  212. static void fnd_seq (f1, beg1, end1, f2, beg2, end2, lngval)
  213.  
  214. FILEINF   *f1;      /* (I) File information for #1. */
  215. int       beg1;     /* (I) First line # to compare in #1. */
  216. int       end1;     /* (I) Last line # to compare in #1. */
  217. FILEINF   *f2;      /* (I) File information for #2. */
  218. int       beg2;     /* (I) First line # to compare in #2. */
  219. int       end2;     /* (I) Last line # to compare in #2. */
  220. int       lngval;   /* (I) "Long enough" value. */
  221. {
  222.     LINEINF      *line1;   /* Line information ptr in #1. */
  223.     LINEINF      *line2;   /* Line information ptr in #2. */
  224.     register int limit;    /* Looping limit. */
  225.     int          ln1;      /* Line number in #1. */
  226.     int          ln2;      /* Line number in #2. */
  227.     register int ln;       /* Working line number. */
  228.     BOOLEAN      go;       /* Continue to loop? */
  229.     int          most;     /* Longest possible seq. */
  230.     int          most1;    /* Longest possible due to #1. */
  231.     int          most2;    /* Longest possible due to #2. */
  232.     int          cnt;      /* Length of longest seq. */
  233.     int          oldcnt;   /* Length of prev longest seq. */
  234.     int          n;        /* Length of cur longest seq. */
  235.     int          m1;       /* Line of longest seq. in #1. */
  236.     int          m2;       /* Line of longest seq. in #2. */
  237.     
  238.     /* Initialize. */
  239.     go    = TRUE;
  240.     line1 = f1->line;
  241.     line2 = f2->line;
  242.  
  243.     /* Initialize longest sequence information. */
  244.     cnt    = 0;          /* Length of longest seq. */
  245.     m1     = beg1 - 1;   /* Line # of longest seq. in #1. */
  246.     m2     = beg2 - 1;   /* Line # of longest seq. in #2. */
  247.     oldcnt = 0;          /* Length of prev longest seq. */
  248.     
  249.     /* Calculate maximum possible number of consecutive */
  250.     /* lines that can match (based on line # ranges).   */
  251.     most1 = end1 - beg1 + 1;
  252.     most2 = end2 - beg2 + 1;
  253.     
  254.     /* Scan lines looking for a "good sequence".
  255.     ** Compare lines in the following order of line numbers:
  256.     **
  257.     **                 (1, 1)
  258.     **         (1, 2), (2, 1), (2, 2)
  259.     ** (1, 3), (2, 3), (3, 1), (3, 2), (3, 3)
  260.     ** etc.
  261.     */
  262.     for (ln1 = beg1, ln2 = beg2; TRUE; ln1++, ln2++)
  263.     {
  264.         if (ln2 <= end2 - cnt)
  265.         /* There are enough lines left in #2 such that it */
  266.         /* is possible to find a longer sequence.         */
  267.         {
  268.             /* Determine the limit in #1 that both       */
  269.             /* enforces the order scheme and still makes */
  270.             /* it possible to find a longer sequence.    */
  271.             limit = min (ln1 - 1, end1 - cnt);
  272.             
  273.             /* Calculate first potential match in #1. */
  274.             for (ln = f1->hashtbl[line2[ln2].hash].frst;
  275.                     ln && ln < beg1; ln = line1[ln].nxtln)
  276.             {
  277.                ;
  278.             }
  279.  
  280.             /* Loop through the lines in #1. */
  281.             for (; ln && ln <= limit; ln = line1[ln].nxtln)
  282.             {
  283.                 if (line1[ln].hash == line2[ln2].hash &&
  284.                         line1[ln + cnt].hash ==
  285.                             line2[ln2 + cnt].hash &&
  286.                         !(ln - m1 == ln2 - m2 &&
  287.                         ln < m1 + cnt && m1 != beg1 - 1))
  288.                 /* A candidate for a longer sequence has */
  289.                 /* been located.  The current lines      */
  290.                 /* match, the current lines + cnt match, */
  291.                 /* and this sequence is not a subset of  */
  292.                 /* the longest sequence so far.          */
  293.                 {
  294.                     /* Calculate most possible matches. */
  295.                     most = min (end1 - ln + 1, most2);
  296.                     
  297.                     /* First compare hash codes.  If the  */
  298.                     /* number of matches exceeds the      */
  299.                     /* longest sequence so far, then      */
  300.                     /* compare the actual text.           */
  301.                     if (chk_hashes (line1 + ln,
  302.                                 line2 + ln2, cnt) &&
  303.                             (n = cnt_matches (f1->txt + ln,
  304.                                 f2->txt + ln2, most)) > cnt)
  305.                     /* This is the longest seq. so far. */
  306.                     {
  307.                         /* Update longest sequence info. */
  308.                         oldcnt = cnt;
  309.                         cnt    = n;
  310.                         m1     = ln;
  311.                         m2     = ln2;
  312.                         
  313.                         /* If it's long enough, end the */
  314.                         /* search.                      */
  315.                         if (cnt >= lngval)
  316.                         {
  317.                             break;
  318.                         }
  319.                         
  320.                         /* Update limit, using new count. */
  321.                         limit = min (ln1 - 1, end1 - cnt);
  322.                     }
  323.                 }
  324.             }
  325.  
  326.             /* If it's long enough, end the search. */
  327.             if (cnt >= lngval)
  328.             {
  329.                 break;
  330.             }
  331.             most2--;
  332.         }
  333.         else
  334.         {
  335.             go = FALSE;   /* This file is exhausted. */
  336.         }
  337.     
  338.         /* Repeat the process for the other file. */    
  339.         if (ln1 <= end1 - cnt)
  340.         {
  341.             limit = min (ln2, end2 - cnt);
  342.             
  343.             for (ln = f2->hashtbl[line1[ln1].hash].frst;
  344.                     ln && ln < beg2; ln = line2[ln].nxtln)
  345.             {
  346.                ;
  347.             }
  348.  
  349.             for (; ln && ln <= limit; ln = line2[ln].nxtln)
  350.             {
  351.                 if (line1[ln1].hash == line2[ln].hash &&
  352.                         line1[ln1 + cnt].hash ==
  353.                             line2[ln+ cnt].hash &&
  354.                         !(ln1 - m1 == ln - m2 &&
  355.                         ln1 < m1 + cnt && m2 != beg2 - 1))
  356.                 {
  357.                     most = min (end2 - ln + 1, most1);
  358.                     
  359.                     if (chk_hashes (line1 + ln1,
  360.                                 line2 + ln, cnt) &&
  361.                             (n = cnt_matches (f1->txt + ln1,
  362.                                 f2->txt + ln, most)) > cnt)
  363.                     {
  364.                         oldcnt = cnt;
  365.                         cnt    = n;
  366.                         m1     = ln1;
  367.                         m2     = ln;
  368.                         
  369.                         if (cnt >= lngval)
  370.                         {
  371.                             break;
  372.                         }
  373.                         
  374.                         limit = min (ln2, end2 - cnt);
  375.                     }
  376.                 }
  377.             }
  378.  
  379.             if (cnt >= lngval)
  380.             {
  381.                 break;
  382.             }
  383.             most1--;
  384.         }
  385.         else if (!go)
  386.         {
  387.             break;   /* This file is exhausted, also. */
  388.         }
  389.     }
  390.  
  391.     /* If the longest sequence is shorter than the "long */
  392.     /* enough" value, the "long enough" value can be     */
  393.     /* adjusted for the rest of the comparison process.  */
  394.     if (cnt < lngval)
  395.     {
  396.         lngval = cnt;
  397.     }
  398.  
  399.     if (cnt >= 1)
  400.     /* Longest sequence exceeds minimum necessary size. */
  401.     {
  402.         if (m1 != beg1 && m2 != beg2 && oldcnt > 0)
  403.         /* There is still something worth comparing */
  404.         /* previous to the sequence.                */
  405.         {
  406.             /* Use knowledge of the previous longest seq. */
  407.             fnd_seq (f1, beg1, m1 - 1,
  408.                     f2, beg2, m2 - 1, oldcnt);
  409.         }
  410.         
  411.         /* Report the sequence. */
  412.         rpt_seq (m1, m2, cnt);
  413.         
  414.         if (m1 + cnt - 1 != end1 && m2 + cnt - 1 != end2)
  415.         /* There is still something worth comparing */
  416.         /* subsequent to the sequence.              */
  417.         {
  418.             fnd_seq (f1, m1 + cnt, end1,
  419.                     f2, m2 + cnt, end2, lngval);
  420.         }
  421.     }
  422. }
  423.  
  424. /***********************************************************
  425. ** chk_hashes determines whether this sequence of matching
  426. ** hash codes is longer than cnt.  It knows that the first
  427. ** pair of hash codes is guaranteed to match.
  428. **
  429. ** RETURNS:  TRUE if this sequence is longer than cnt.
  430. **           FALSE if this sequence is not longer than cnt.
  431. ***********************************************************/
  432.  
  433. static BOOLEAN chk_hashes (line1, line2, cnt)
  434.  
  435. LINEINF        *line1;   /* (I) Line information for #1. */
  436. LINEINF        *line2;   /* (I) Line information for #2. */
  437. register int   cnt;      /* (I) Count to try to exceed. */
  438. {
  439.     register int   n;   /* Count of consecutive matches. */
  440.  
  441.     for (n = 1; n <= cnt &&
  442.         ((++line1)->hash == (++line2)->hash); n++)
  443.     {
  444.         ;
  445.     }
  446.  
  447.     return (n > cnt);
  448. }
  449.  
  450. /***********************************************************
  451. ** cnt_matches counts the number of consecutive matching
  452. ** lines of text.
  453. **
  454. ** RETURNS:  number of consecutive matching lines.
  455. ***********************************************************/
  456.  
  457. static int cnt_matches (s1, s2, most)
  458.  
  459. char         **s1;   /* (I) Starting line in file #1. */
  460. char         **s2;   /* (I) Starting line in file #2. */
  461. register int most;   /* (I) Most matching lines possible. */
  462. {
  463.     register int   n;   /* Count of consecutive matches. */
  464.  
  465.     /* Count the consecutive matches. */
  466.     for (n = 0; n < most && strcmp (*s1++, *s2++) == ALIKE;
  467.             n++)
  468.     {
  469.         ;
  470.     }
  471.     
  472.     return (n);
  473. }
  474.  
  475. /***********************************************************
  476. ** rpt_seq reports a matching sequence of lines.
  477. ***********************************************************/
  478.  
  479. static void rpt_seq (m1, m2, cnt)
  480.  
  481. int   m1;    /* (I) Location of matching sequence in #1. */
  482. int   m2;    /* (I) Location of matching sequence in #2. */
  483. int   cnt;   /* (I) Number of lines in matching sequence. */
  484. {
  485.     fprintf (stdout,
  486.         "Matched %5d lines:  (%5d - %5d) and (%5d - %5d)\n",
  487.          cnt, m1, m1 + cnt - 1, m2, m2 + cnt - 1);
  488. }
  489.